#include <bits/stdc++.h>

using namespace std;
const int N = 1000 + 10, inf = 0x3f3f3f3f;
int f[N][N], n, m;
int dist[N];
bool vis[N];
int dijkstra() {
	memset(dist, inf, sizeof dist);
	dist[1] = 0;
	for (int i = 1; i <= n; i++){
		int t=-1;
		for(int j = 1; j <= n; j++){
			if(!vis[j] && (t == -1 || dist[t] > dist[j]))t = j;
		}
		vis[t] = true;
		for(int j = 1; j <= n; j++){
			if(vis[j])continue;
			if(dist[j] > dist[t] + f[t][j])dist[j] = dist[t] + f[t][j];
		}
	}
	if(dist[n] == inf)return -1;
	return dist[n];
}
int main(){
	memset(f, inf, sizeof f);
	cin >> n >> m;
	while (m--) {
		int a, b, c;
		cin  >> a >> b >> c;
		f[a][b] = min(f[a][b], c);
	}
	cout << dijkstra();
}
